package com.wang.sort3;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @Author: along
 * @Create: 2021/4/22
 * @Description:并查集结构
 */
public class Demo06_UnionFind {
    public static class Node<V> {
       V value;

       public Node(V v) {
           this.value = v;
       }
    }
    public static class UnionSet<V> {
        public HashMap<V, Node<V>> nodes; //节点的对应表
        public HashMap<Node<V>, Node<V>> parents;//节点的代表点 这里成为parents
        public HashMap<Node<V>, Integer> sizeMap;//代表点的map的长度
        //初始化
        public UnionSet(List<V> values) {
            for (V value: values
                 ) {
                Node<V> node = new Node<>(value);
                nodes.put(value, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        public boolean isSameSet(V a, V b ) {
            if(!nodes.containsKey(a) || !nodes.containsKey(b)){
                return false;
            }
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        public void union(V a, V b) {
            if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
                return;
            }
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if(aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                if(aSetSize >= bSetSize) {
                    parents.put(bHead, aHead);
                    sizeMap.put(aHead, aSetSize + bSetSize);
                    parents.remove(bHead);
                }
                else {
                    parents.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize + bSetSize);
                    parents.remove(aHead);
                }
            }
        }

        private Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();//初始化一个栈，来保存遍历过程中代表点为同一个的节点
            //从cur开始，一直往上找，找到不能往上的节点，即为代表点，返回
            while (cur != parents.get(cur)) {
                path.push(cur);
                cur = parents.get(cur);
            }
            //上面的while跳出后，cur一定来到代表点
            //优化
            while (!path.isEmpty()) {
                //返回cur之前，把所有的遍历到的代表点为cur的节点在parents中的代表节点改为cur
                parents.put(path.pop(), cur);
            }
            return cur;
        }
    }


}
